\label{chap:discuss}
During experiments with the algorithm, an interesting case has been found. For the graph \emph{strcon8.in} our modification of the original R-Greedy algorithm~\cite{pub:Gleiss} proved to produce a smaller basis of independent circuits, thus proving that the algorithm as described in~\cite{pub:Gleiss} does not, in fact, produce a minimal circuit base. Such a different result has been obtained only in the case of the \emph{strcon8.in} graph. For all the other processed graphs (e.g. graphs listed in chapter~\ref{chap:tests}) the results of modified and original R-Greedy algorithm were the same.

\section{Modified R-Greedy algorithm}
In the original R-Greedy algorithm the first circuit having a certain weight value was always added to the $B_{=}$ and $R_{=}$ sets, and so this circuit was always included in the final set of relevant circuits and in the minimal circuit basis. Our modification was to test such a circuit for linear dependence just like all the other circuits.

\newpage
\lstset{caption={Modified \emph{R-Greedy} algorithm implementation in \emph{Python} language.}, label={code:RGreedyMod}}
\begin{lstlisting}[frame=tb]
def r_greedy(circuits):
	circuits.sort(key = attrgetter("weight"))
	b_less = []
	relevant = []
	prev_circuit = circuits[0]
	r_equal = [prev_circuit]
	b_equal = [prev_circuit]
	for circuit in circuits[1:]:
		if circuit.weight > prev_circuit.weight:
			relevant.extend(r_equal)
			b_less.extend(b_equal)
			r_equal = []
			b_equal = []
		if independent([circuit] + b_less):
			r_equal.append(circuit)
		if independent([circuit] + b_less + b_equal):
			b_equal.append(circuit)
		prev_circuit = circuit
	relevant.extend(r_equal)
	b_less.extend(b_equal)
	return (b_less, relevant)
\end{lstlisting}


\section{Results}
\subsection{The \emph{strcon8} graph}
\begin{figure}[htb]
\begin{center}
\includegraphics[width=150px]{strcon8}
\caption{option \emph{-d} output: \emph{strcon8.in}}
\label{discuss:strcon8in}
\end{center}
\end{figure}

\subsection{Original R-Greedy results}
Minimal circuit base proposed by original R-Greedy:
\begin{verbatim}
[([0, 1, 2]: 3.0), ([0, 1, 7]: 3.0), ([0, 6, 7]: 3.0), ([1, 2, 3]: 3.0),
 ([2, 3, 4]: 3.0), ([3, 4, 5]: 3.0), ([4, 5, 6]: 3.0), ([5, 6, 7]: 3.0),
 ([0, 6, 4, 2]: 4.0), ([0, 6, 7, 5, 3, 4, 2]: 7.0)]
Size: 10, weights sum: 35.000000
\end{verbatim}

\noindent Set of relevant circuits proposed by original R-Greedy:
\begin{verbatim}
[([0, 1, 2]: 3.0), ([0, 1, 7]: 3.0), ([0, 6, 7]: 3.0), ([1, 2, 3]: 3.0),
 ([2, 3, 4]: 3.0), ([3, 4, 5]: 3.0), ([4, 5, 6]: 3.0), ([5, 6, 7]: 3.0),
 ([0, 6, 4, 2]: 4.0), ([1, 7, 5, 3]: 4.0), ([0, 6, 7, 5, 3, 4, 2]: 7.0)]
Size: 11, weights sum: 39.000000
\end{verbatim}

\subsection{Modified R-Greedy results}
Minimal circuit base:
\begin{verbatim}
[([0, 1, 2]: 3.0), ([0, 1, 7]: 3.0), ([0, 6, 7]: 3.0), ([1, 2, 3]: 3.0),
 ([2, 3, 4]: 3.0), ([3, 4, 5]: 3.0), ([4, 5, 6]: 3.0), ([5, 6, 7]: 3.0),
 ([0, 6, 4, 2]: 4.0)]
Size: 9, weights sum: 28.000000
\end{verbatim}

\noindent Set of relevant circuits:
\begin{verbatim}
[([0, 1, 2]: 3.0), ([0, 1, 7]: 3.0), ([0, 6, 7]: 3.0), ([1, 2, 3]: 3.0),
 ([2, 3, 4]: 3.0), ([3, 4, 5]: 3.0), ([4, 5, 6]: 3.0), ([5, 6, 7]: 3.0),
 ([0, 6, 4, 2]: 4.0), ([1, 7, 5, 3]: 4.0)]
Size: 10, weights sum: 32.000000
\end{verbatim}

\subsection{Analysis of results}
The actual, produced by our modified algorithm, minimal circuit base doesn't contain the circuit $([0, 6, 7, 5, 3, 4, 2]: 7.0)$. Also the relevant circuits set doesn't contain two circuits proposed by the original algorithm. However, the circuit $([0, 6, 4, 2]: 4.0)$ remained in the minimal circuit base, that's because it can't be expressed as a linear combination of smaller circuits, even if they contain all the necessary edges. The two following subsections provide actual matrices containing vectors from cycle space and their reduced row echelon form, showing why the circuit $([0, 6, 7, 5, 3, 4, 2]: 7.0)$ was removed and the circuit $([0, 6, 4, 2]: 4.0)$ retained.

\newpage
\subsection{Case of retain}
The new circuit is independent with $B_{<}$ (all rows of the reduced row echelon form of cycle space matrix are non-zero). Each row of presented original matrix is a circuit, while each column represents a directed edge. For easier analysis, columns are labelled.
\begin{verbatim}
-----  CIRCUIT processed:  -----
([0, 6, 4, 2]: 4.0)

B< (min base)
[([0, 1, 2]: 3.0), ([0, 1, 7]: 3.0), ([0, 6, 7]: 3.0), ([1, 2, 3]: 3.0),
 ([2, 3, 4]: 3.0), ([3, 4, 5]: 3.0), ([4, 5, 6]: 3.0), ([5, 6, 7]: 3.0)]

B= :
[]
\end{verbatim}

\begin{verbatim}
check independent(circuit, B<)
  0:1 0:6 1:2 1:7 2:0 2:3 3:1 3:4 4:2 4:5 5:3 5:6 6:4 6:7 7:0 7:5 
[[ 0.  1.  0.  0.  1.  0.  0.  0.  1.  0.  0.  0.  1.  0.  0.  0.]
 [ 1.  0.  1.  0.  1.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 1.  0.  0.  1.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  0.]
 [ 0.  1.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  1.  0.]
 [ 0.  0.  1.  0.  0.  1.  1.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  1.  0.  1.  1.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  1.  0.  1.  1.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  0.  1.  1.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  0.  1.  0.  1.]]
\end{verbatim}
\begin{verbatim}
Matrix after GJ elimination:
[[ 1.  0.  0.  0.  0.  0. -1.  0.  0.  0. -1.  0.  0.  0.  1. -1.]
 [ 0.  1.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  1.  0.]
 [-0. -0.  1.  0.  0.  0.  1.  0. -1.  0.  1.  0. -1.  1.  0.  1.]
 [ 0.  0.  0.  1.  0.  0.  1.  0.  0.  0.  1.  0.  0.  0.  0.  1.]
 [-0. -0. -0. -0.  1. -0. -0. -0.  1. -0. -0. -0.  1. -1. -1. -0.]
 [ 0.  0.  0.  0.  0.  1.  0.  0.  1.  0. -1.  0.  1. -1.  0. -1.]
 [ 0.  0.  0.  0.  0.  0.  0.  1.  0.  0.  1.  0. -1.  1.  0.  1.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  0.  0.  1. -1.  0. -1.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  0.  1.  0.  1.]]
(circuit, B<) are INDEPENDENT
\end{verbatim}

\newpage
\subsection{Case of removal}
The new circuit is dependent (last row of the matrix is zeroed).
\begin{verbatim}
-----  CIRCUIT processed:  -----
([0, 6, 7, 5, 3, 4, 2]: 7.0)

B< (min base)
[([0, 1, 2]: 3.0), ([0, 1, 7]: 3.0), ([0, 6, 7]: 3.0), ([1, 2, 3]: 3.0),
 ([2, 3, 4]: 3.0), ([3, 4, 5]: 3.0), ([4, 5, 6]: 3.0), ([5, 6, 7]: 3.0),
 ([0, 6, 4, 2]: 4.0)]
\end{verbatim}

\begin{verbatim}
check independent(circuit, B<)
  0:1 0:6 1:2 1:7 2:0 2:3 3:1 3:4 4:2 4:5 5:3 5:6 6:4 6:7 7:0 7:5 
[[ 0.  1.  0.  0.  1.  0.  0.  1.  1.  0.  1.  0.  0.  1.  0.  1.]
 [ 1.  0.  1.  0.  1.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 1.  0.  0.  1.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  0.]
 [ 0.  1.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  1.  0.]
 [ 0.  0.  1.  0.  0.  1.  1.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  1.  0.  1.  1.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  1.  0.  1.  1.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  0.  1.  1.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  0.  1.  0.  1.]
 [ 0.  1.  0.  0.  1.  0.  0.  0.  1.  0.  0.  0.  1.  0.  0.  0.]]
\end{verbatim}
\begin{verbatim}
Matrix after GJ elimination:
[[ 1.  0.  0.  0.  0.  0. -1.  0.  0.  0. -1.  0.  0.  0.  1. -1.]
 [ 0.  1.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  1.  0.]
 [-0. -0.  1.  0.  0.  0.  1.  0. -1.  0.  1.  0. -1.  1.  0.  1.]
 [ 0.  0.  0.  1.  0.  0.  1.  0.  0.  0.  1.  0.  0.  0.  0.  1.]
 [-0. -0. -0. -0.  1. -0. -0.  0.  1.  0.  0.  0.  1. -1. -1.  0.]
 [ 0.  0.  0.  0.  0.  1.  0.  0.  1.  0. -1.  0.  1. -1.  0. -1.]
 [ 0.  0.  0.  0.  0.  0.  0.  1.  0.  0.  1.  0. -1.  1.  0.  1.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  0.  0.  1. -1.  0. -1.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  0.  1.  0.  1.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]]
\end{verbatim}

